//
// Created by hay boy on 2022/7/10.
//

#ifndef ALGORITHMS_SORTEDARRAYLIST_H
#define ALGORITHMS_SORTEDARRAYLIST_H

#include "dictionary.h"

template<class K,class E>
struct pairPack{
    typedef pair<const K,E> pairType;
    ~pairPack(){
        (*ele).~pairType();
    }
public:
    pairType *ele;
    explicit pairPack(const pairType& thePair):ele(&thePair){}
    pairPack()= default;
};
template<class K,class E>
class SortedArrayList:public Dictionary<K,E>{
protected:
    pairPack<K,E>* element;
    int dSize;
    int dTotalSize;
public:
    explicit SortedArrayList(int initialCapacity=10);
    bool empty() const{
        return dSize==0;
    }

    int size() const{
        return dSize;
    }

    pair<const K,E>* find(const K&)const;
    void erase(const K&);
    void insert(const pair<const K, E> );
    virtual void clear();
private:
    virtual void reInsert(const pair<const K, E> &, bool);

};

template<class K, class E>
void SortedArrayList<K, E>::clear() {
    for(int i = 0;i<dSize;i++){
        element[i].~pairPack();
    }
    dSize = 0;
}

template<class K, class E>
SortedArrayList<K, E>::SortedArrayList(int initialCapacity) {
    element = new pairPack<K,E>[initialCapacity];
    dTotalSize = initialCapacity;
}

template<class K, class E>
pair<const K, E> *SortedArrayList<K, E>::find(const K &theKey)const {
    for(int i = 0;i<dSize;i++){
        if(theKey==(*(element[i].ele)).first){
            return &(*(element[i].ele));
        }
    }
    return nullptr;
}

template<class K, class E>
void SortedArrayList<K, E>::erase(const K &theKey) {
    for(int i = 0;i<dSize;i++){
        if(theKey==(*(element[i].ele)).first){
            copy(element+i+1,element+dSize,element+i);
            return;
        }
    }
}

template<class K, class E>
void SortedArrayList<K, E>::insert(const pair<const K, E> thePair) {
    bool exist = find(thePair.first)!=nullptr;
    if(exist){
        for(int i = 0;i<dSize;i++){
            if((*(element[i].ele)).first==thePair.first){
                (*(element[i].ele)).second = thePair.second;
            }
        }
    }else{
        if(dSize==dTotalSize){
            pairPack<K,E>* newElement = new pairPack<K,E>[dTotalSize*2];
            copy(element,element+dTotalSize,newElement);
            delete[] element;
            element = newElement;
            dTotalSize *= 2;
        }
        reInsert(thePair, true);
    }
}

template<class K, class E>
void SortedArrayList<K, E>::reInsert(const pair<const K, E> &thePair, bool checked) {
    int i;
    for(i = 0;i<dSize&&thePair.first<(*(element[i].ele)).first;i++){}
    copy_backward(element+i+1,element+dSize,element+i+2);
    element[i+1] = pairPack<K,E>(thePair);
}
#endif
